
typedef struct QueueNode {
    int val;
    struct QueueNode* next;
    struct QueueNode* prev;
} QueueNode;

typedef struct MyCircularDeque {
    QueueNode* head;
    QueueNode* end;
} MyCircularDeque;

QueueNode* BuyNode(int val) {
    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    node->val = val;
    node->next = node->prev = NULL;
    return node;
}

MyCircularDeque* myCircularDequeCreate(int k) {
    MyCircularDeque* queue = (MyCircularDeque*)malloc(sizeof(MyCircularDeque));
    queue->head = queue->end = BuyNode(1001);
    queue->head->next = queue->head;
    queue->head->prev = queue->head;
    for (int i = 0; i < k; ++i) {
        QueueNode* newnode = BuyNode(1001);
        queue->end->next = newnode;
        newnode->prev = queue->end;
        newnode->next = queue->head;
        queue->head->prev = newnode;
        queue->end = newnode;
    }
    queue->end = queue->head;
    return queue;
}

bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
    return obj->head == obj->end;
}

bool myCircularDequeIsFull(MyCircularDeque* obj) {
    return obj->head->prev == obj->end;
}

bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
    if (myCircularDequeIsFull(obj))
        return false;
    obj->head->val = value;
    obj->head = obj->head->prev;
    return true;
}

bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
    if (myCircularDequeIsFull(obj))
        return false;
    obj->end->next->val = value;
    obj->end = obj->end->next;
    return true;
}

bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj))
        return false;
    obj->head = obj->head->next;
    return true;
}

bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj))
        return false;
    obj->end = obj->end->prev;
    return true;
}

int myCircularDequeGetFront(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj))
        return -1;
    return obj->head->next->val;
}

int myCircularDequeGetRear(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj))
        return -1;
    return obj->end->val;
}

void myCircularDequeFree(MyCircularDeque* obj) {
    QueueNode* cur = obj->head->next;
    while (cur != obj->head) {
        QueueNode* next = cur->next;
        free(cur);
        cur = NULL;
        cur = next;
    }
    free(obj->head);
}

/**
 * Your MyCircularDeque struct will be instantiated and called as such:
 * MyCircularDeque* obj = myCircularDequeCreate(k);
 * bool param_1 = myCircularDequeInsertFront(obj, value);
 
 * bool param_2 = myCircularDequeInsertLast(obj, value);
 
 * bool param_3 = myCircularDequeDeleteFront(obj);
 
 * bool param_4 = myCircularDequeDeleteLast(obj);
 
 * int param_5 = myCircularDequeGetFront(obj);
 
 * int param_6 = myCircularDequeGetRear(obj);
 
 * bool param_7 = myCircularDequeIsEmpty(obj);
 
 * bool param_8 = myCircularDequeIsFull(obj);
 
 * myCircularDequeFree(obj);
*/